
/**
 * // Definition for a Node.
 * function Node(val,left,right) {
 *    this.val = val;
 *    this.left = left;
 *    this.right = right;
 * };
 */
/**
 * @param {Node} root
 * @return {Node}
 */
//? 因为搜索树的中序遍历的顺序是我们所需链表的顺序。
//? 因此使用深度优先搜索进行中序遍历。
//? 遍历结束，依次赋值前驱后驱即可，头尾特殊处理。

var treeToDoublyList = function(root) {
    const dfs = (root) => {
        return root ? [...dfs(root.left), root, ...dfs(root.right)] : []
    }
    //? 拿到中序遍历结果
    const arr = dfs(root)
    //? 依次赋值 头尾特殊
    for (let i = 0; i < arr.length; i++) {
        if (i === arr.length - 1) {
            arr[0].left = arr[arr.length - 1]
            arr[arr.length - 1].right = arr[0]
        } else {
            arr[i].right = arr[i + 1]
            arr[i + 1].left = arr[i]
        }
    }
    return arr[0]
};

